import C03A4

def sort(list):
    node=list.first()
    newList = C03A4.List()
    while node!=None:
        insert(newList,node)
        node=list.next(node)
    return newList

def insert(list,insertNode):
    node=list.first()
    while node!=None:
        if node.data>insertNode.data:
            list.insertBefore(node,insertNode.data)
            return
        node=list.next(node)
    list.insertAsLast(insertNode.data)

list = C03A4.List()
for i in range(20):
    list.insertAsLast(20-i)

node=list.first()
while node!=None:
    print(node.data)
    node=list.next(node)
print('=================')
newList=sort(list)
node=newList.first()
print("newList.size====",newList.size)
while node!=None:
    print(node.data)
    node=newList.next(node)
    